package 链表;

/**
 * 力扣19
 *
 * @Author zxl
 * @Date 2022/1/14 20:54
 * @Desc 删除链表中倒数第n个节点（n从1开始）
 */
public class 删除倒数第n个节点 {

    /**
     * 初始化链表
     *
     * @return
     */
    public static Node initData() {
        Node node1 = new Node();
        node1.value = 1;
        Node node2 = new Node();
        node2.value = 2;
        Node node3 = new Node();
        node3.value = 3;
        Node node4 = new Node();
        node4.value = 4;
        Node node5 = new Node();
        node5.value = 5;

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        return node1;
    }

    public static void main(String[] args) {

        Node head = initData();
        int n = 2;
        System.out.println("删除前：" + head.toString());
        deleteByTowPointer(head, n);
        System.out.println("删除后：" + head.toString());

    }


    /**
     * o o o o o
     *
     * @param head
     * @param n
     * @return
     */
    public static void deleteByTowPointer2(Node head, int n) {
        // 计算是正数滴几
        Node headTemp = head;
        while (n != 0) {
            headTemp = headTemp.next;
            n--;
        }
        while (headTemp.next != null) {
            head = head.next;
            headTemp = headTemp.next;
        }
        head.next = head.next.next;
    }


    /**
     * 双指针
     *
     * @param head
     * @param n
     */
    public static void deleteByTowPointer(Node head, int n) {

        Node fasterNode = head, slowerNode = head;
        while (n != 0) {
            fasterNode = fasterNode.next;
            n--;
        }
        // 让slower节点走到删除节点的前一个
        while (fasterNode.next != null) {
            fasterNode = fasterNode.next;
            slowerNode = slowerNode.next;
        }
        slowerNode.next = slowerNode.next.next;
    }

    /**
     * 第一次遍历找出删除节点的正向位置，第二次遍历删除操作
     * {@link 删除倒数第n个节点}
     *
     * @param head
     * @param n
     * @return
     */
    public static void deleteNode(Node head, int n) {
        int length = 0;
        Node curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }
        // 删除节点的前一个节点的坐标
        int deleteIndex = length - n;
        Node pre = head;
        while (pre.value != deleteIndex) {
            pre = pre.next;
        }
        pre.next = pre.next.next;
    }
}
